package algorithm.KMP;

class Sort {
    public static void main(String[] args) {
        int[] nums = {9, 2, 7, 0, 5, 3, 1, 6, 4, 8};
        mergeSort(nums, 0, nums.length-1);
        for (int x : nums) {
            System.out.print(x + " ");
        }
        System.out.println();
    }
    private static void quickSort(int[] nums, int left, int right) {
        if(left >= right) {
            return;
        }
        int i = left, j = right;
        int base = nums[left];
        while(i < j) {
            while(i < j && nums[j] >= base) {
                --j;
            }
            nums[i] = nums[j];
            while(i < j && nums[i] <= base) {
                ++i;
            }
            nums[j] = nums[i];
        }
        nums[i] = base;
        quickSort(nums, left, i - 1);
        quickSort(nums, i + 1, right);
    }
    private static void mergeSort(int[] nums, int left, int right) {
        if(left < right) {
            int mid = (left + right) / 2;
            mergeSort(nums, left, mid);
            mergeSort(nums, mid+1, right);
            merge(nums, left, mid, right);
        }
    }
    private static void merge(int[] nums, int left, int mid, int right) {
        int[] temp = new int[right-left+1];
        int i = left, j = mid + 1, t = 0;
        while(i <= mid && j <= right) {
            if(nums[i] <= nums[j]) {
                temp[t++] = nums[i++];
            } else {
                temp[t++] = nums[j++];
            }
        }
        while(i <= mid) {
            temp[t++] = nums[i++];
        }
        while(j <= right) {
            temp[t++] = nums[j++];
        }
        i = left;
        while(i <= right) {
            nums[i] = temp[i-left];
            i++;
        }
    }
}
